package leetcode101.complex_datastructure;

/**
 * @author Synhard
 * @version 1.0
 * @class Code2
 * @description 765. 情侣牵手
 * N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。
 * 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。
 *
 * 人和座位用 0 到 2N-1 的整数表示，情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2N-2, 2N-1)。
 *
 * 这些情侣的初始座位  row[i] 是由最初始坐在第 i 个座位上的人决定的。
 *
 * 示例 1:
 *
 * 输入: row = [0, 2, 1, 3]
 * 输出: 1
 * 解释: 我们只需要交换row[1]和row[2]的位置即可。
 * 示例 2:
 *
 * 输入: row = [3, 2, 0, 1]
 * 输出: 0
 * 解释: 无需交换座位，所有的情侣都已经可以手牵手了。
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-07-02 15:32
 */
public class Code2 {
    public int minSwapsCouples(int[] row) {
        DSU4Code2 dsu = new DSU4Code2(row.length);
        int couples = row.length >> 1;
        for (int i = 0; i < row.length - 1; i++) {
            dsu.union(row[i] >> 1, row[i + 1] >> 1);
        }
        return couples - dsu.getCount();
    }
}

class DSU4Code2 {
    private int[] parent; // 父节点
    private int count; // 记录连通分量的个数

    public int getCount() {
        return count;
    }

    public DSU4Code2(int n) {
        this.count = n;
        this.parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    public int find(int x) {
        while (x != parent[x]) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return;
        }
        parent[rootX] = rootY; // 如果相邻两个人不是情侣则说明不是一个连通分量，合并这两个情侣互相所在的联通分量，使联通分量减一
        count--;
    }
}
/*
仔细分析可得
最少的交换次数 = 情侣总对数 - 已经坐对位置的情侣个数
 */